package com.hj.sort;

import java.util.Arrays;

/**
 * @author hj
 * @Date 2022/1/5
 * @Description: 希尔排序(增写缩量 - 直接插入排序)
 */
public class ShellSort {

    public void shellSort(int[] array) {
        if (null == array) {
            return;
        }
        int gap = array.length;
        do {
            // 增量每次减半
            gap /= 2;
            for (int i = 0; i < gap; i++) {
                // 这个循环里其实就是一个插入排序
                for (int j = i + gap; j < array.length; j += gap) {
                    int k = j - gap;
                    while (k >= 0 && array[k] > array[k + gap]) {
                        int temp = array[k];
                        array[k] = array[k + gap];
                        array[k + gap] = temp;
                        k -= gap;
                    }
                }
            }
        } while (gap != 1);
    }

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] array = {5, 9, 125, 6, 85, 97, 45, 3, 25, 64, 36, 98, 103, 45, 12, 35};
        shellSort.shellSort(array);
        System.out.println(Arrays.toString(array));
    }


}
